The halting problem is undecidable --- but can it be solved for "most"inputs? This natural question was considered in a number of papers, indifferent settings. We revisit their results and show that most of them can beeasily proven in a natural framework of optimal machines (considered inalgorithmic information theory) using the notion of Kolmogorov complexity. Wealso consider some related questions about this framework and about asymptoticproperties of the halting problem. In particular, we show that the fraction ofterminating programs cannot have a limit, and all limit points are Martin-L\"ofrandom reals. We then consider mass problems of finding an approximate solutionof halting problem and probabilistic algorithms for them, proving both positiveand negative results. We consider the fraction of terminating programs thatrequire a long time for termination, and describe this fraction using the busybeaver function. We also consider approximate versions of separation problems,and revisit Schnorr's results about optimal numberings showing how they can begeneralized.
展开▼
